The present invention relates to the rendering of object graphic elements into raster pixel images and, in particular, to efficient rendering of such elements to pixel image data without the use of frame or line storage of the pixel data as part of the rendering process.
Most object based graphics systems utilise a frame store or page buffer to hold a pixel-based image of the page or screen. Typically, the outlines of the graphic objects are calculated, filled and written into the frame store. For two-dimensional graphics, objects which appear in front of other objects are simply written into the frame store after the background objects, thereby replacing the background on a pixel-by-pixel basis. This is commonly known in the art as the xe2x80x9cPainter""s algorithmxe2x80x9d. Objects are considered in priority order, from the rearmost object to the foremost object, and, typically, each object is rasterised in scan line order and pixels are written to the frame store in sequential runs along each scan line.
There are essentially two problems with this technique. The first is that it requires fast random access to all the pixels in the frame store. This is because each new object considered could affect any pixel in the frame-store. For this reason, the frame store is normally kept in semiconductor random access memory (RAM). For high resolution colour printers the amount of RAM required is very large, typically in excess of 100 MBytes, which is costly and difficult to operate at high speed. The second problem is that many pixels which are painted (rendered), are over-painted (re-rendered) by later objects. Painting the pixels with the earlier objects was a waste of time.
One method for overcoming the large frame-store problem is the use of xe2x80x9cbandingxe2x80x9d. When banding is used, only part of the frame-store exists in memory at any one time. All of the objects to be drawn are retained in a xe2x80x9cdisplay listxe2x80x9d. The whole image is rendered as above, but pixel painting (rendering) operations that try to paint (render) outside the fraction of the frame-store which exists are xe2x80x9cclippedxe2x80x9d out. After all the objects have been drawn, the fractional part of the frame-store is sent to the printer (or some other location) and another fraction of the frame-store is selected and the process repeated. There are penalties with this technique. For example, the objects being drawn must be considered and re-considered many timesxe2x80x94once for each band. As the number of bands increases, so too does the repetitious examination of objects requiring rendering. The technique of banding does not solve the problem of the cost of over-painting.
Some other graphic systems consider the image in scan line order. Again, all the objects to be drawn are retained in a display list. On each scan line the objects which intersect that scan line are then considered in priority order and for each object, spans of pixels between object edge intersection points are set in a line store. This technique also overcomes the large frame store problem, but still suffers from the over-paint problem.
There are other techniques which overcome both the large frame-store problem and the over-painting problem. In one such technique, each scan line is produced in turn. Again, all the objects to be drawn are retained in a display list. On each scan line, the edges of objects which intersect that scan line are held in order of increasing coordinate of intersection with the scan line. These points of intersection, or edge crossings, are considered in turn and used to toggle an array of active flags. There is one active flag for each object priority which is of interest on the scan line. Between each pair of edges considered, the colour data for each pixel which lies between the first edge and the next edge is generated by using a priority encoder on the active flags to determine which priority is topmost, and using the colour associated with that priority for the pixels of the span between the two edges. In preparation for the next scan line, the coordinate of intersection of each edge is updated in accordance with the nature of each edge. Adjacent edges which become mis-sorted as a result of this update are swapped. New edges are also merged into the list of edges.
This technique has the significant advantages that there is no frame store or line store, there is no over painting, and the object priorities are dealt with in constant order time, rather than order N time (where N is the number of priorities).
However, there are several limitations to this technique:
(i) The technique only supports the xe2x80x9codd-evenxe2x80x9d fill rule, known in the art for determining the inside versus outside state of an object from its edges. The xe2x80x9cnon-zero windingxe2x80x9d fill rule, which is a required feature of many graphic description languages, is not supported by that technique.
(ii) Large mis-sorting can occur for which a simple swapping technique is inadequate to repair. While a brute-force sort of the whole of the edge list on each scan line can be performed, this is very slow.
(iii) The technique does not support raster (pixel-based) images as an object type. Such images are a required feature of most graphic description languages.
(iv) The technique only supports objects which are opaque, where each painted pixel strictly obscures the pixels of objects with lesser priority. The technique does not support raster operations in which the colour of two or more graphic objects interact. Such operations include drawing in XOR mode, or the compositing of partially transparent objects. These modification operations are a required feature of most graphic description languages.
(v) The technique does not support clipping, where one or more clip shapes suppress some number of other graphics objects inside (or outside) the bounds of the clip shapes. Clipping is a required feature of most graphic description languages.
(vi) The technique uses voluminous and inefficient encoding of object edges, particularly for text. It is desirable for such an extremely common element of graphic descriptions to be represented in a simpler fashion.
(vii) The technique in some instances does not provide for accurate evaluation of complicated compositing expressions where the activity of one or more objections is variable.
The inability of the technique to implement many features required by existing graphic description languages severely limits its use.
Further, some existing rendering interfaces require implementation of the bit-wise logical combination of the colour of two or more graphic objects. Other existing rendering interfaces require implementation of an alpha channel (also referred to as transparency, opacity, or matte) based combination of the colour of two or more graphic objects. Current techniques do not allow these two features to be implemented in a unified fashion.
It is an object of the present invention to substantially overcome, or at least ameliorate, one or more deficiencies with prior art systems.
In accordance with one aspect of the present invention there is disclosed a method of processing graphic objects intended to form a raster pixel image, said processing comprising a process for determining an intersection order between edges of said graphic objects by evaluating corresponding edge records for a current scan line in rasterised display order and determining an edge intersection value for each said edge for a subsequent scan line, said process comprising, during processing of said edge records, the steps of:
retaining a limited number of processed edge records in an unordered first buffer and progressively transferring said processed edge records to a second buffer in order, as orderable processed edge records are added to said first buffer;
transferring unorderable processed edge records to a third buffer in order to order said edge records in said third buffer; and
selectively processing edge records from said second and third buffers for determining ordered intersections for a subsequent scan line.
In accordance with another aspect of the present invention there is disclosed a method of processing graphic objects intended to form a raster pixel image in a graphic object rendering system, said processing comprising a first process for determining an intersection order between edges of said graphic objects and a current scan line of said raster pixel image, said system comprising:
plural edge records for each of a current scan line and a subsequent scan line, each of said records including a plurality of record locations for retaining at least a pixel location value of a corresponding edge on the corresponding scan line, each of said current and subsequent edge records being divided into at least a main portion and a spill portion, at least the main portion of said current edge records being arranged in raster pixel order;
at least one current active edge record;
a spill active edge record, and
a pool including a limited predetermined number of edge records; said method comprising the steps of:
(a) transferring a first edge record from each of said main and spill portions of said current edge records into the corresponding active edge records;
(b) comparing values of said active edge records to determine that said active edge record having a lowest value in said raster pixel order and outputting that value and record as a current edge value and record;
(c) updating said current edge record with a value of the corresponding edge for said subsequent scan line;
(d) comparing the updated edge value with edge values within said pool, wherein if the updated edge value is less than an edge value in said pool then
(da) said updated current edge record is transferred to the spill portion of the subsequent edge records; otherwise
(db) (dba) an edge record having a smallest edge value is transferred from said pool to a next record of the main portion of said subsequent edge record; and
(dbb) said updated edge record is transferred to the record of said pool vacated in sub-step (dba); and
(dc) a further edge record is transferred from the corresponding portion of the current edge record to the active edge record vacated by the updated edge record;
(e) repeating steps (b) to (d) until each of said records in said pool are occupied whereupon a smallest edge value record of said pool is transferred to said main portion of said subsequent edge records;
(f) repeating steps (b) to (e) until all records of said current records have been updated, and then flushing records from said pool in order to respective next records within said main portion of said subsequent records;
(g) sorting said records in said spill portion of said subsequent records into raster pixel order;
(h) transferring said subsequent edge records to said current edge records; and
(i) repeating steps (a) to (h) for each further scan line of said raster pixel image.
In accordance with another aspect of the present invention there is disclosed apparatus for processing graphic objects intended to form a raster pixel image, said processing comprising a process for determining an intersection order between edges of said graphic objects by evaluating corresponding edge records for a current scanline in rasterised display order and determining an edge intersection value for each said edge for a subsequent scanline, said apparatus comprising:
a memory having an unordered first buffer, a second buffer and a third buffer; and
a processor for retaining a limited number of processed edge records in said unordered first buffer, for progressively transferring said processed edge records to said second buffer in order, as orderable processed edge records are added to said first buffer, for transferring unorderable processed edge records to said third buffer in order to order said edge records in said third buffer, and for selectively processing edge records from said second and third buffers for determining ordered intersections for a subsequent scanline.
In accordance with another aspect of the present invention there is disclosed apparatus for processing graphic objects intended to form a raster pixel image, said processing comprising a process for determining an intersection order between edges of said graphic objects by evaluating corresponding edge records for a current scan line in rasterised display order and determining an edge intersection value for each said edge for a subsequent scan line, said apparatus comprising:
means for retaining a limited number of processed edge records in an unordered first buffer and progressively transferring said processed edge records to a second buffer in order, as orderable processed edge records are added to said first buffer;
means for transferring unorderable processed edge records to a third buffer in order to order said edge records in said third buffer; and
means for selectively processing edge records from said second and third buffers for determining ordered intersections for a subsequent scan line.
In accordance with another aspect of the present invention there is disclosed a computer readable memory medium for storing a program for apparatus which processes graphic objects intended to form a raster pixel image, said processing comprising a process for determining an intersection order between edges of said graphic objects by evaluating corresponding edge records for a current scan line in rasterised display order and determining an edge intersection value for each said edge for a subsequent scan line, said program comprising:
code for a retaining step for retaining a limited number of processed edge records in an unordered first buffer and progressively transferring said processed edge records to a second buffer in order, as orderable processed edge records are added to said first buffer;
code for a transfer step for transferring unorderable processed edge records to a third buffer in order to order said edge records in said third buffer; and
code for a process step for selectively processing edge records from said second and third buffers for determining ordered intersections for a subsequent scan line.
Other aspects of the present invention will be apparent from the following description.